package BinaryTree;

//时间复杂度: O(n)
public class Coded {
	    // Encodes a tree to a single string.

		public static int MAXN=10001;
		
		public static TreeNode[] queue=new TreeNode[MAXN];
		
		public static int l,r;
		
	    public String serialize(TreeNode root) {
	    	StringBuilder builder=new StringBuilder();
	    	//为了实现按层序列化，因此在插入队列时就需要将节点值进行序列化
	    	if(root!=null) {
	    		l=r=0;
                builder.append(root.val+",");
	    		queue[r++]=root;
	    		while(l<r) {
	    			TreeNode cur=queue[l++];
	    			if(cur.left==null) {
	    				builder.append("#,");
	    			}
	    			else {
                        builder.append(cur.left.val+",");
	    				queue[r++]=cur.left;
	    			}
	    			if(cur.right==null) {
	    				builder.append("#,");
	    			}
	    			else {
                        builder.append(cur.right.val+",");
	    				queue[r++]=cur.right;
	    			}
	    		}
	    	}
	    	return builder.toString();
	    }
	    

	    // Decodes your encoded data to tree.
	    public TreeNode generate(String val) {  //构造节点
	    	return val.equals("#")?null:new TreeNode(Integer.valueOf(val));
	    }
	    public TreeNode deserialize(String data) {
	    	if(data.equals("")) {
	    		return null;
	    	}
	        String[] vals=data.split(",");
	        l=r=0;
	        int index=0;   //第index个节点
	        TreeNode root=generate(vals[index++]);
	        queue[r++]=root;
	        while(l<r) {
	        	TreeNode cur=queue[l++];
	        	//构造左右孩子
	        	cur.left=generate(vals[index++]); 
	        	cur.right=generate(vals[index++]);
	        	//左右孩子不为空则入队列，处理下一个节点
	        	if(cur.left!=null) {
	        		queue[r++]=cur.left;
	        	}
	        	if(cur.right!=null) {
	        		queue[r++]=cur.right;
	        	}
	        }
	        return root;
	    }
}
